package com.yun.algorithmproblem.leetcode;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 3264. K 次乘运算后的最终数组 I
 *
 * 给你一个整数数组 nums ，一个整数 k  和一个整数 multiplier 。
 *
 * 你需要对 nums 执行 k 次操作，每次操作中：
 *
 * 找到 nums 中的 最小 值 x ，如果存在多个最小值，选择最 前面 的一个。
 * 将 x 替换为 x * multiplier 。
 * 请你返回执行完 k 次乘运算之后，最终的 nums 数组。
 */
public class Leetcode3264 {

    public static void main(String[] args) {
        Leetcode3264 obj = new Leetcode3264();
        int[] nums=new int[]{2,1,3,5,6};
        int k =5;
        int multiplier = 2;
        int[] res = obj.getFinalState(nums, k, multiplier);
        System.out.println(Arrays.toString(res));
    }

    public int[] getFinalState(int[] nums, int k, int multiplier) {
        PriorityQueue<int[]> heap = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0] == 0?o1[1]-o2[1]:o1[0]-o2[0];
            }
        });
        for (int i = 0; i < nums.length; i++) {
            heap.add(new int[]{nums[i],i});
        }
        for (int i = 0; i < k; i++) {
            int[] poll = heap.poll();
            poll[0]*=multiplier;
            heap.add(poll);
        }
        for (int i = 0; i < nums.length; i++) {
            int[] poll = heap.poll();
            nums[poll[1]]=poll[0];
        }
        return nums;
    }
}
